package com.example.demo.leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 活动选择问题
 * 无重复区间个数
 * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。
 * 返回 需要移除区间的最小数量，使剩余区间互不重叠 。
 * 示例 1:
 * <p>
 * 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
 * 输出: 1
 * 解释: 移除 [1,3] 后，剩下的区间没有重叠。
 */

// 贪心算法
//    1）局部最优。每一步都做出在当前看来是最优的选择
//    2）全局最优。通过局部的最优，最终使得全局最优
//    3）无需回溯。一旦做出选择，不会回头重新考虑之前的选择，效率很高
//  1.优先选择 活动时间最短的，不行的
//  2.需要先统计冲突次数，然后优先选择冲突次数最少的活动 ，也不行的
//  3.优选选择最先开始的活动，也不行
//  4.优先选择最先结束（结束时间最早的）的活动，哎居然行了 好神奇！！！
//    选择结束时间最早的活动，能给其他活动留出更多的时间，从而可以选择最多的活动
public class Leetcode435 {

    static class Act {
        int start;
        int end;

        public Act(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "Act{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

    public static int eraseOverlapIntervals(int[][] intervals) {
        Act[] acts = new Act[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            acts[i] = new Act(start, end);
        }
        //                System.out.println(Arrays.toString(acts));
        //                System.out.println(maxActivities(acts));
        return acts.length - maxActivities(acts);
    }

    private static int maxActivities(Act[] acts) {
        // 贪心算法 优选选择最早结束的 end最小的
        Arrays.sort(acts, Comparator.comparingInt(a -> a.end));
        int count = 1;
        Act prev = acts[0];

        for (int i = 1; i < acts.length; i++) {
            Act curr = acts[i];
            if (curr.start >= prev.end) {
                count++;
                prev = curr;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] inputArray = {
                {1, 2},
                {2, 3},
                {3, 4},
                {1, 3}
        };

        eraseOverlapIntervals(inputArray);

    }
}
